package com.lft.tree12.union_find_disjoint_sets;

/**
 * 并查集
 */
public class UnionFindDisjointSets {
	public static void main(String[] args) {
		UnionFindImpl unionFind = new UnionFindImpl(10);
		System.out.println("合并前：");
		unionFind.printArr();
		
		unionFind.unionElements(0, 1);
		unionFind.unionElements(0, 4);
		unionFind.unionElements(6, 9);
		
		System.out.println("合并后：");
		unionFind.printArr();
		
	}
}

/**
 * 实现方式三：存储每个节点的父节点值,添加 rank 存储以每一节点为根节点的树的深度。
 */
class UnionFindImpl implements UnionFindInterface {
	private int[] parent;
	/**
	 * 存储以每一节点为根节点的树的深度。
	 */
	private int[] rank;
	
	public UnionFindImpl(int size) {
		parent = new int[size];
		rank = new int[size];
		for (int i = 0; i < parent.length; i++) {
			// 初始时每个节点自成一个集合，所以父节点就是自己。
			parent[i] = i;
			// 初始时每个节点自成一个集合，所以树的深度都为1
			rank[i] = 1;
		}
	}
	
	/**
	 * 优化3：路径压缩2
	 * 查找节点 p 的根节点
	 * 时间复杂度O(h)，h为树的高度
	 */
	private int find(int p) {
		if (p >= 0 && p < parent.length) {
			if (p != parent[p]) {
				// 路径压缩：递归设计父节点。
				parent[p] = find(parent[p]);
			}
			return parent[p];
		} else {
			throw new IllegalArgumentException("参数非法！");
		}
	}
	
	// /**
	//  * 优化2：路径压缩1
	//  * 查找节点 p 的根节点
	//  * 时间复杂度O(h)，h为树的高度
	//  */
	// private int find(int p) {
	// 	if (p >= 0 && p < parent.length) {
	// 		while (p != parent[p]) {
	// 			// 路径压缩：将当前节点的父节点，设置成父节点的父节点。
	// 			parent[p] = parent[parent[p]];
	// 			p = parent[p];
	// 		}
	// 		return p;
	// 	} else {
	// 		throw new IllegalArgumentException("参数非法！");
	// 	}
	// }
	
	// /**
	//  * 查找节点 p 的根节点
	//  * 时间复杂度O(h)，h为树的高度
	//  */
	// private int find(int p) {
	// 	if (p >= 0 && p < parent.length) {
	// 		while (p != parent[p]) {
	// 			p = parent[p];
	// 		}
	// 		return p;
	// 	} else {
	// 		throw new IllegalArgumentException("参数非法！");
	// 	}
	// }
	
	/**
	 * 判断是否为同一集合
	 * 只需要比较是否是相同的根。
	 */
	@Override
	public boolean isConnection(int p, int q) {
		return find(p) == find(q);
	}
	
	/**
	 * 合并元素到同一集合
	 * 优化1：使用 rank 记录节点的深度。
	 * @param p 要合并的元素
	 * @param q 目标集合元素
	 */
	@Override
	public void unionElements(int p, int q) {
		int pRoot = find(p);
		int qRoot = find(q);
		// 如果 p q 处在相同集合，不需要处理
		if (pRoot == qRoot) {
			return;
		}
		// 将深度小的树 添加到深度大的树中，需要更新 rank 值
		if (rank[pRoot] < rank[qRoot]) {
			parent[pRoot] = qRoot;
		} else if (rank[pRoot] > rank[qRoot]) {
			parent[qRoot] = pRoot;
		} else {
			// 相同深度的两棵树，可以随意添加，但是 rank 需要更新（+1即可）
			parent[pRoot] = qRoot;
			rank[pRoot] += 1;
		}
	}
	
	@Override
	public int getSize() {
		return parent.length;
	}
	
	public void printArr() {
		System.out.print("索引\t\t");
		for (int i = 0; i < this.parent.length; i++) {
			System.out.print(i + "\t");
		}
		System.out.println();
		System.out.print("集合\t\t");
		for (int id : this.parent) {
			System.out.print(id + "\t");
		}
		System.out.println();
	}
}

// /**
//  * 实现方式二：存储每个节点的父节点值
//  */
// class UnionFindImpl implements UnionFindInterface {
//	/**
//	 * 存储每个节点的父节点值
//	 */
// 	private int[] parent;
//
// 	public UnionFindImpl(int size) {
// 		parent = new int[size];
// 		for (int i = 0; i < parent.length; i++) {
// 			// 初始时每个节点自成一个集合，所以父节点就是自己。
// 			parent[i] = i;
// 		}
// 	}
//
// 	/**
// 	 * 查找节点 p 的根节点
// 	 * 时间复杂度O(h)，h为树的高度
// 	 */
// 	private int find(int p) {
// 		if (p >= 0 && p < parent.length) {
// 			while (p != parent[p]) {
// 				p = parent[p];
// 			}
// 			return p;
// 		} else {
// 			throw new IllegalArgumentException("参数非法！");
// 		}
// 	}
//
// 	/**
// 	 * 判断是否为同一集合
// 	 * 只需要比较是否是相同的根。
// 	 */
// 	@Override
// 	public boolean isConnection(int p, int q) {
// 		return find(p) == find(q);
// 	}
//
// 	/**
// 	 * 合并元素到同一集合
// 	 * @param p 要合并的元素
// 	 * @param q 目标集合元素
// 	 */
// 	@Override
// 	public void unionElements(int p, int q) {
// 		int pRoot = find(p);
// 		int qRoot = find(q);
// 		// 如果 p q 处在相同集合，不需要处理
// 		if (pRoot ==qRoot) {
// 			return;
// 		}
// 		// 将 pRoot 添加到 qRoot 中。成为 qRoot 的孩子。
// 		parent[pRoot] = qRoot;
// 	}
//
// 	@Override
// 	public int getSize() {
// 		return parent.length;
// 	}
// public void printArr() {
// 	System.out.print("索引\t\t");
// 	for (int i = 0; i < this.parent.length; i++) {
// 		System.out.print(i + "\t");
// 	}
// 	System.out.println();
// 	System.out.print("集合\t\t");
// 	for (int id : this.parent) {
// 		System.out.print(id + "\t");
// 	}
// 	System.out.println();
// }
// }

//
// /**
//  * 实现方式一：存储每个数据所属集合的编号
//  */
// class UnionFindImpl implements UnionFindInterface {
// 	/**
// 	 * 存储每个数据所属集合的编号
// 	 * 下标表示 自身值
// 	 * 值表示 集合号
// 	 */
// 	private int[] id;
//
// 	public UnionFindImpl(int size) {
// 		id = new int[size];
// 		for (int i = 0; i < id.length; i++) {
// 			// 开始时，让每个元素构成一个单元素的集合。
// 			id[i] = i;
// 		}
// 	}
//
// 	@Override
// 	public boolean isConnection(int p, int q) {
// 		return find(p) == find(q);
// 	}
//
// 	private int find(int p) {
// 		if (p >= 0 && p < id.length) {
// 			return id[p];
// 		} else {
// 			throw new IllegalArgumentException("参数不合法!");
// 		}
// 	}
//
// 	/**
// 	 * 合并元素。
// 	 * @param p 要合并的元素
// 	 * @param q 目标集合元素
// 	 */
// 	@Override
// 	public void unionElements(int p, int q) {
// 		int pId = find(p);
// 		int qId = find(q);
// 		// 待合并的两个集合 id 一样。说明在同一个集合中。无需操作。
// 		if (pId == qId) {
// 			return;
// 		}
// 		for (int i = 0; i < id.length; i++) {
// 			if (id[i] == pId) {
// 				id[i] = qId;
// 			}
// 		}
// 	}
//
// 	@Override
// 	public int getSize() {
// 		return id.length;
// 	}
//	public void printArr() {
// 		System.out.print("索引\t\t");
// 		for (int i = 0; i < this.parent.length; i++) {
// 			System.out.print(i + "\t");
// 		}
// 		System.out.println();
// 		System.out.print("集合\t\t");
// 		for (int id : this.parent) {
// 			System.out.print(id + "\t");
// 		}
// 		System.out.println();
// 	}
// }

/**
 * 并查集接口。
 * 带三俱抽像方法。
 */
interface UnionFindInterface {
	/**
	 * 判断是否连通
	 */
	boolean isConnection(int p, int q);
	
	/**
	 * 合并节点。
	 */
	void unionElements(int p, int q);
	
	/**
	 * 获取节点数
	 * @return
	 */
	int getSize();
}